package io.gitee.wiqer.simple;

import io.gitee.wiqer.ListNode;
import org.junit.Test;

import java.util.HashMap;
import java.util.concurrent.ThreadLocalRandom;

public class SolutionNC4_HasCycle {
    /**
     *
     * 判断一个链表是否有环
     *
     * HashMap
     *
     * @param head
     * @return
     */
    public boolean hasCycle_1(ListNode head) {

        HashMap<ListNode, Integer> hm = new HashMap<ListNode, Integer>();
        while (head != null) {
            if (hm.get(head) == null) {
                hm.put(head, 1);
            } else {
                return true;
            }
            head = head.next;
        }
        return false;
    }


    /**
     *
     * 快慢指针
     *
     * @param head
     * @return
     */
    public boolean hasCycle_2(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) { // 只需判断fast即可
            count++;
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    /**
     *
     * 来过
     *
     * @param head
     * @return
     */
    public boolean hasCycle_3(ListNode head) {

        ListNode current = head;
        while (current != null) { // 只需判断fast即可
            count++;
            if (current.pass) {
                return true;
            }
            current.pass=true;
            current=current.next;
        }
        return false;
    }

    /**
     * 计数器，方便估算时间复杂度
     */
    int count=0;
    @Test
    public void test(){
        int sum=100;
        int masterNodeVal= ThreadLocalRandom.current().nextInt()&0x7fffffff%sum;
        int slaveNodeVal= ThreadLocalRandom.current().nextInt()&0x7fffffff%sum;
        ListNode masterNode=null;
        ListNode slaveNode=null;
        ListNode next = null;
        ListNode current=null;
        for (int i = 0; i <sum;i++ ) {
            current=new ListNode(i);
            current.next=next;
            next=current;
            if(i==masterNodeVal){
                masterNode=current;
            }else  if(i==slaveNodeVal){
                slaveNode=current;
            }
        }
        masterNode.next=slaveNode;
        hasCycle_3(current);
        System.out.println(count);
    }
}
